/**
 * https://leetcode-cn.com/problems/path-sum/
 * 判断从根到叶子节点的总和为指定的数字
 * @param root 
 * @param targetSum 
 */
const hasPathSum = (root: TreeNode | null, targetSum: number): boolean => {
    // 树为空, 不存在值为targetSum
    if (root === null) return false

    /**
     * 判断是不是叶子节点
     * @param n 
     */
    const isLeaf = (n: TreeNode) => n.left === null && n.right === null

    // 使用两个队列, 分别存储节点和当前节点对应的和
    const nodes: TreeNode[] = [root],
        vals: number[] = [root.val];

    // 直到队列为空
    while (nodes.length > 0) {
        // 从队列弹出元素
        const n = nodes.shift()!,
              v = vals.shift()!;

        // 判断当前节点是不是叶子节点
        if (isLeaf(n)) {
            // 当前节点总和等于了要找的值
            if (v === targetSum) return true;
        }

        // 没找到所要的值

        // 左子树存在
        if (n.left !== null) {
            nodes.push(n.left)
            // 值相加
            vals.push(v + n.left.val)
        }

        // 右子树存在
        if (n.right !== null) {
            nodes.push(n.right);
            vals.push(v + n.right.val)
        }
    }

    // 都没找到, 返回false
    return false
};

// 递归
const hasPathSum2 = (root: TreeNode | null, targetSum: number): boolean => {
    // 树为空, 不存在值为targetSum
    if (root === null) return false

    /**
     * 判断是不是叶子节点
     * @param n 
     */
    const isLeft = (n: TreeNode) => n.left === null && n.right === null

    /**
     * 寻找
     * @param n 
     */
    const find = (n: TreeNode | null, left: number): boolean => {
        // 找到根还没找到, 说明找不到
        if (n === null) return false

        // 该节点是叶子节点并且值是相等的
        if (n.val === left && isLeft(n)) return true;

        // 找到说明n.val < targetSum

        // 找左边
        let l = find(n.left, left - n.val);

        // 左边找到, 直接返回true
        if (l) return true

        // 找右边
        let r = find(n.right, left - n.val);

        // 右边的结果
        return r
    }

    return find(root, targetSum);
};